/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/maximum-subarray-iii
   @Language: C++
   @Datetime: 16-02-09 09:02
   */

class Solution {
public:
	/**
	 * @param nums: A list of integers
	 * @param k: An integer denote to find k non-overlapping subarrays
	 * @return: An integer denote the sum of max k non-overlapping subarrays
	 * Tip:
	 * local[i][k] : max sum, include nums[i]
	 * global[i][k]: max sum, exclude nums[i]
	 */
	int maxSubArray(vector<int> nums, int k) {
		// write your code here
		int n=nums.size();
		vector<vector<int> > global(n+1,vector<int>(k+1,INT_MIN));
		vector<vector<int> > local(n+1,vector<int>(k+1,INT_MIN));
		for(int i=1;i<=k;++i)
			local[0][i]=0;
		for(int i=1;i<=n;++i){
			global[i][0]=local[i][0]=0;
			for(int j=1;j<=k &&j<=i;++j){
				local[i][j]=max(local[i-1][j]+nums[i-1],global[i-1][j-1]+nums[i-1]);
				global[i][j]=max(global[i-1][j],local[i][j]);
			}
		}
		return global[n][k];
	}
};
